// 1192. [塔杨DFS/连通分量] 查找集群内的关键连接
// https://leetcode.cn/problems/critical-connections-in-a-network/
// Tarjan算法是用来求有向图的强连通分量的,求双连通分量的Tarjan算法,【Tarjan算法是基于对图深度优先搜索的】
// 每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，
// 回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
// 力扣数据中心有 n 台服务器，分别按从 0 到 n-1
// 的方式进行了编号。它们之间以「服务器到服务器」
// 点对点的形式相互连接组成了一个内部集群，其中连接 connections
// 是无向的。从形式上讲， connections[i] = [a, b] 表示服务器 a 和 b
// 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。
// 关键连接是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。
// 请你以任意顺序返回该集群内的所有 「关键连接」。
// 输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
// 输出：[[1,3]]
// 解释：[[3,1]] 也是正确的。
// 输入：n = 2, connections = [[0,1]]
// 输出：[[0,1]]
#include <bits/stdc++.h>
using namespace std;
//#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif
class Solution {
 private:
  vector<bool> mVis;
  vector<int> mDfn;  // 记录每次的timeStamp
  vector<int> mLow;  // [i]这棵树能触碰到的最小的Dfn
  int timeStamp = 0;
  vector<vector<int>> mConnects;
  vector<vector<int>> mRes;

 public:
  void paramInit(int nodeCnt) {
    timeStamp = 0;
    for (int i = 0; i < nodeCnt; ++i) {
      mVis.push_back(false);
      mDfn.push_back(0);
      mLow.push_back(0);
      mConnects.push_back(vector<int>());
    }
  }
  void tarjan(int curNode, int preNode) {
    mVis[curNode] = true;
    mDfn[curNode] = mLow[curNode] = ++timeStamp;
    PF("node=%d, v=%d,dfn=%d,low=%d\n", curNode, mVis[curNode], mDfn[curNode],
       mLow[curNode]);
    for (size_t toNode = 0; toNode < mConnects[curNode].size(); ++toNode) {
      if (mVis[mConnects[curNode][toNode]] == false) {
        tarjan(mConnects[curNode][toNode], curNode);
        mLow[curNode] = min(mLow[curNode], mLow[mConnects[curNode][toNode]]);
        if (mDfn[curNode] < mLow[mConnects[curNode][toNode]]) {
          mRes.push_back({curNode, mConnects[curNode][toNode]});
        }
      } else if (mConnects[curNode][toNode] != preNode) {
        mLow[curNode] = min(mLow[curNode], mDfn[mConnects[curNode][toNode]]);
      }
    }
  }

 public:
  vector<vector<int>> criticalConnections(int nodeCnt,
                                          vector<vector<int>>& connections) {
    paramInit(nodeCnt);
    for (size_t i = 0; i < connections.size(); ++i) {
      mConnects[connections[i][0]].push_back(connections[i][1]);
      mConnects[connections[i][1]].push_back(connections[i][0]);
    }
    tarjan(0, -1);
    return mRes;
  }
};